package algorithm_demo.demo05;

/**
 * N皇后问题
 *
 * @author Api
 * @date 2023/3/19 9:59
 */
public class Code08_NQueens01 {
    /*
        N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上
        给定一个整数n，返回n皇后的摆法有多少种。
        n=1，返回1
        n=2或3,2皇后和3皇后问题无论怎么摆都不行，返回0
        n=8，返回92
    */

    /**
     * @param i      当前行
     * @param record 记录已经放皇后的位置 record[0]=7，表示0行的皇后在7列
     * @param n      代表一共多少行 0-N-1行有效
     * @return 多少中摆法
     */
    public static int process1(int i, int[] record, int n) {
        //base case
        if (i == n) {
            return 1;
        }
        int res = 0;
        //未到终止位置,h还有皇后要摆
        //当前行在i行，尝试所有的列 -> j
        for (int j = 0; j < n; j++) {
            if (isValid(record, i, j)) {
                record[i] = j;
                res += process1(i + 1, record, n);
                //这里为什么不加还原现场的操作
                //record[i] = j;因为这里面直接进入就是修改值，可以不还原
            }
        }
        return res;
    }

    /**
     * 共列，共斜线问题
     *
     * @param record 数组，记录为 <下标表示行，值表示列>
     * @param i 行
     * @param j 列
     * @return boolean值，判断是否共列，共斜线
     */
    public static boolean isValid(int[] record, int i, int j) {
        //之前的某个K行的皇后
        //k只需要遍历i-1,i行上面的位置
        for (int k = 0; k < i; k++) {
            //k表示行，列为record[k]
            //j == record[k]共列
            //Math.abs(record[k] - j) == Math.abs(i - k) 共斜线
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }
}
